package mydsl;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class LinkedBinaryTree<E> extends AbstractContainer<E> implements BinaryTree<E> {
	private BTNode<E> root; // 根节点
	private int size; // 节点数量
	
	// 构造一个空二叉树
	public LinkedBinaryTree() {
		this.root = null;
		this.size = 0;
	}
	
	public int size() {
		return this.size;
	}
	
	public Position<E> root() {
		return this.root;
	}
	
	public Position<E> addRoot(E e) {
		if(!isEmpty())
			throw new IllegalArgumentException("Tree already has a root");
		this.root = new BTNode<E>(e, null, null, null);
		this.size = 1;
		return this.root;
  }
	
	protected BTNode<E> checkPosition(Position<E> v) 
	    throws IllegalArgumentException {
		if (v == null || !(v instanceof BTNode))
			throw new IllegalArgumentException("The position is invalid");
		return (BTNode<E>) v;
	}
	
	public Position<E> left(Position<E> v) {
		BTNode<E> nv = checkPosition(v);
		return nv.getLeft();
	}

	public Position<E> right(Position<E> v) {
		BTNode<E> nv = checkPosition(v);
		return nv.getRight();
	}

	public Position<E> parent(Position<E> v) {
		BTNode<E> nv = checkPosition(v);
		return nv.getParent();
	}
	
	public boolean isInternal(Position<E> v) {
		BTNode<E> nv = checkPosition(v);
		return (nv.hasLeft() || nv.hasRight());
	}
	
	public boolean isExternal(Position<E> v) {
		return !isInternal(v);
	}

	// 对于二叉树而言，每个节点最多有两个孩子
	public Iterator<Position<E>> children(Position<E> v) {
		BTNode<E> nv = checkPosition(v);
		List<Position<E>> list = new LinkedList<Position<E>>();
		if(nv.hasLeft())
			list.add(nv.getLeft());
		if(nv.hasRight())
			list.add(nv.getRight());
		return list.iterator();
	}

	public E replace(Position<E> v, E e) {
		BTNode<E> nv = checkPosition(v);
		E temp = nv.element();
		nv.setElement(e);
		return temp;
	}

	public Position<E> insertLeft(Position<E> v, E e) {
		BTNode<E> nv = checkPosition(v);
		if(nv.hasLeft())
			throw new IllegalArgumentException("Node already has a left child");
		BTNode<E> lv = new BTNode<E>(e, nv, null, null);
		nv.setLeft(lv);
		return lv;
	}
	
	public Position<E> insertRight(Position<E> v, E e) {
		BTNode<E> nv = checkPosition(v);
		if(nv.hasRight())
			throw new IllegalArgumentException("Node already has a left child");
		BTNode<E> lv = new BTNode<E>(e, nv, null, null);
		nv.setRight(lv);
		return lv;
	}
	
	public Iterator<E> iterator() {
		return iteratorLevelOrder(); // 默认使用宽度遍历
	}
	
	public Iterator<E> iteratorPreOrder() {
		return iterator();
	}
	
	public Iterator<E> iteratorInOrder() {
		List<E> elements = new LinkedList<E>();
		if(size != 0)
		      inorder(this.root, elements);
		return elements.iterator();	
	}
	
	public Iterator<E> iteratorPostOrder() {
		List<E> elements = new LinkedList<E>();
		if(size != 0)
		      postorder(this.root, elements);
		return elements.iterator();	
	}
	
	// 前序遍历
	protected void preorder(Position<E> v, List<E> elements) {
		BTNode<E> nv = checkPosition(v);
	    elements.add(nv.element());
	    if (nv.hasLeft())
	      preorder(nv.getLeft(), elements); // 遍历左节点
	    if (nv.hasRight())
	      preorder(right(v), elements);		// 遍历右节点
	}
	
	// 中序遍历
	protected void inorder(Position<E> v, List<E> elements) {
		BTNode<E> nv = checkPosition(v);
	    if (nv.hasLeft())
	    	preorder(nv.getLeft(), elements);	// 遍历左节点
	    elements.add(nv.element());
	    if (nv.hasRight())
	    	preorder(right(v), elements);		// 遍历右节点
	}
	
	// 后序遍历
	protected void postorder(Position<E> v, List<E> elements) {
		BTNode<E> nv = checkPosition(v);
	    if (nv.hasLeft())
	    	preorder(nv.getLeft(), elements);	// 遍历左节点
	    if (nv.hasRight())
	    	preorder(right(v), elements);		// 遍历右节点
	    elements.add(nv.element());
	}
	
	// 宽度遍历
	public Iterator<E> iteratorLevelOrder() {
		List<E> elements = new LinkedList<E>();
		Queue<Position<E>> q = new LinkedList<Position<E>>();
		q.add(this.root);
		while(!q.isEmpty()) {
			BTNode<E> node = (BTNode<E>)q.poll();
			elements.add(node.element());
			if(node.hasLeft())
				q.add(node.getLeft());
			if(node.hasRight())
				q.add(node.getRight());
		}
		return elements.iterator();
	}
	
	public void expandExternal (Position<E> v) throws IllegalAccessException {
		BTNode<E> nv = checkPosition(v);
		nv.expand();
		this.size += 2;
	}
	
	public String toString(){
		return ToString.stringfor(this);
//		return super.toString(this.iteratorLevelOrder());
	}
}
